Search engines are commonly used to search large linked databases, such as the World Wide Web, for desired content and to sort the search results in a ranked fashion based on some measure of relevancy. Such a database can be represented as a directed graph of N nodes, where each node corresponds to a document and where the directed connections between nodes correspond to directed links from one document to another.
One approach to ranking is based on the intrinsic content of the documents or document links. Another approach is the page rank method, which determines a ranking from the link structure of the directed graph. In this approach, the rank of a web page is related to the probability that a web surfer ends up at the page after randomly following a large number of links. The page ranks for the database are calculated by finding the principal eigenvector of an N×N link matrix A, where each element αij of A represents a probability of moving from node i to node j of a directed graph of N nodes.
The principal eigenvector may be computed using the power method, an iterative procedure that calculates the steady-state probability vector x defined as the vector to which xn=Anx0 converges as n grows very large, where x0 is an initial N-dimensional vector. The rank xk for a node k is simply the kth component of the vector x. A singular value decomposition of A may be calculated to define the rank of a node as the corresponding component of the singular vector. The probabilities in the matrix A often depend on a parameter and a given distribution over pages and thus the page rank values depend on these quantities. The affect of both of these quantities on the mathematics of the page rank vector are fairly well understood, with α being selected as a single deterministic value.